package com.yun.datastructure.tree.binarysearchtree.leetcode;

import com.yun.datastructure.tree.binarytree.domain.TreeNode;

import java.util.LinkedList;

public class Leetcode98 {
    public boolean isValidBST2(TreeNode root) {
        LinkedList<TreeNode> stack=new LinkedList<>();
        TreeNode p=root;
        long prev=Long.MIN_VALUE;
        while (p!=null||!stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.left;
            }else {
                TreeNode pop=stack.pop();
                //值
                if(pop.val<=prev){
                    return false;
                }
                prev=pop.val;
                p=pop.right;
            }
        }
        return true;
    }

    long prev=Long.MIN_VALUE;
    public boolean isValidBST1(TreeNode node){
        if(node==null){
            return true;
        }
        boolean a=isValidBST1(node.left);
        if(!a){
            return false;
        }
        //值
        if(node.val<=prev){
            return false;
        }
        prev=node.val;
        return isValidBST1(node.right);
    }

    public boolean isValidBST(TreeNode node){
        return doValid(node,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean doValid(TreeNode node,long min,long max){
        if(node==null){
            return true;
        }
        if(node.val<=min||node.val>=max){
            return false;
        }
        if(!doValid(node.left,min,node.val)){
            return false;
        }
        return doValid(node.right,node.val,max);
    }
}
